package com.LeeCode;

/**
 * 按字典序排列最小的等效字符串
 */

public class Code1061 {
    public static void main(String[] args) {
        String s1 = "parker";
        String s2 = "morris";
        String baseStr = "parser";
        System.out.println(new Code1061().smallestEquivalentString(s1, s2, baseStr));
    }

    public String smallestEquivalentString(String s1, String s2, String baseStr) {
        // 初始化并查集：每个字母 a-z 对应索引 0-25
        int[] parent = new int[26];
        for (int i = 0; i < 26; i++) {
            parent[i] = i; // 初始每个字符的父节点是它自己
        }

        // 遍历所有字符对，建立等价关系
        for (int i = 0; i < s1.length(); i++) {
            int a = s1.charAt(i) - 'a'; // 字符转索引
            int b = s2.charAt(i) - 'a';

            int rootA = find(a, parent); // 找到 a 所属集合的根
            int rootB = find(b, parent); // 找到 b 所属集合的根

            if (rootA != rootB) {
                // 合并两个集合，总是将较大的字符合并到较小字符的集合中
                int minRoot = Math.min(rootA, rootB);
                parent[rootA] = minRoot;
                parent[rootB] = minRoot;
            }
        }

        // 构造结果字符串
        StringBuilder sb = new StringBuilder();
        for (char c : baseStr.toCharArray()) {
            int idx = c - 'a';
            int root = find(idx, parent); // 找到当前字符所属集合的最小字符
            sb.append((char) ('a' + root)); // 转换为对应字符
        }

        return sb.toString();
    }

    /**
     * 并查集查找函数（带路径压缩）
     * @param x 当前字符索引（0-25）
     * @param parent 父节点数组
     * @return 当前字符所在集合的根节点
     */
    private int find(int x, int[] parent) {
        while (parent[x] != x) {
            // 路径压缩：把当前节点直接指向祖父节点
            parent[x] = parent[parent[x]];
            x = parent[x]; // 继续向上查找
        }
        return x;
    }
}
